import java.util.*;

public class LRUReplacement {
    //最近最少使用算法
    public static int lackTimes;
    public double replace(int[] pagesSequence, int memoryBlocks){
        //记录缺页次数
        lackTimes = 0;
        //当前页框数
        int[] memory = new int[memoryBlocks];
        //当前的位置
        int curIndex = 0;
        //将所有的内存块置为-1为空闲状态
        for (int i = 0;i<memoryBlocks;i++){
            memory[i]=-1;
        }
        //定义LinkedHashMap记录最近使用的内存块并设置最大的容量以移除不常使用的块
        Map<Integer,Integer> linkedHashMap =
                new LinkedHashMap<Integer,Integer>(16, 0.75f, true) {
                 // 设置大小为最大内存块
                    @Override
                    protected boolean removeEldestEntry(java.util.Map.Entry eldest) {
                        return size() > memoryBlocks;
                    }
                };
        //获取LinkedHashMap中的值
        Set<Integer> set ;

        //在内存中寻找页，找到则不操作，没找到则实施替换操作
        for (int i = 0;i<pagesSequence.length;i++){
            if(searchIndex(0,pagesSequence[i],memory)!=-1){
                //找到也要更新linkedHashMap
                linkedHashMap.get(pagesSequence[i]);
            }
            else{
                //此时内存块有剩余，不计算缺页率
                if(memory[memory.length-1] == -1){
                    linkedHashMap.put(pagesSequence[i],pagesSequence[i]);
                    memory[curIndex] = pagesSequence[i];
                    curIndex++;
                }
                //内存块已满开始记录缺页次数
                else{
                    //记录缺页次数
                    lackTimes++;
                    //将linkedHashMap转换为List方便取值
                    set = linkedHashMap.keySet();
                    List<Integer> list = new ArrayList<>(set);
                    //获取最不常使用的页，为linkedHashMap中的第一个
                    int tail = list.get(0);
                    //在内存块中找到并替换最不常使用的页
                    int indexTemp = searchIndex(0,tail,memory);
                    curIndex = indexTemp;
                    memory[curIndex] = pagesSequence[i];
                    //将最新放入的页更新到linkedHashMap
                    linkedHashMap.put(pagesSequence[i],pagesSequence[i]);
                }

            }

        }
        //返回缺页率
        return (lackTimes * 1.0/pagesSequence.length);
    }

    //从startIndex开始，返回最先出现的位置
    public int searchIndex(int startIndex, int page, int[] pagesSquence) {
        for(int i=startIndex;i<pagesSquence.length;i++){
            if(page==pagesSquence[i]){
                return i;
            }
        }
        return -1;
    }
}
